package DataStructure.LinkedLearning.DoublyLinkedList.LinearList;

/**
 *  使用内部类封装链表
 */
public class MyDoubleLinked {
    // 头尾指针
    private Node head;
    private Node tail;
    private int size;

    /**
     *  添加功能
     * @param str 新节点的内容
     * @return 返回成功与否
     */
    public boolean add(String str) {
        // 判断传入参数是否为空，是则报错
        if (str == null){
            throw  new NullPointerException("The parame is null");
        }
        Node node = new Node(null, str, null);
        // 判断链表是否为空
        if (size == 0){
            // 将头尾指针指向新节点
            head = node;
            tail = node;
            size++;
            return true;
        }
        tail.next = node;
        node.pre = tail;
        tail = node;
        size++;
        return true;
    }

    /**
     *  根据下标添加一个元素
     * @param index : 下标位置
     * @param str : 添加的元素
     * @return : 添加是否成功
     */
    public boolean add(int index, String str){
        // 验证参数 添加时参数可以等于size值，表示添加到最后
        if (index < 0 || index > size) {
            throw  new IllegalArgumentException("index is Illegal");
        }
        Node node = new Node(null, str, null);
        // 添加头结点
        if (index == 0){
            // 当链表原本为空时
            if (size == 0){
                head = node;
                tail = node;
            } else {
                // 当链表原本非空时
                node.next = head;
                head.pre = node;
                head = node;
            }
            size++;
            return true;
        }
        // 新增在尾结点
        if (index == size){
            add(str);
            return true;
        }
        // 添加的不是头结点 也不是尾结点
        Node mid = head;
        // 判断插入位置靠近头部或尾部
        if (index > size/2) {
            int tag = size;
            mid = tail;
            while (tag != index){
                mid = mid.pre;
                tag--;
            }
        } else {// 接近于头部
            int tag = 1;
            mid = head;
            while (tag != index){
                mid = mid.next;
                tag++;
            }
        }
         //把结点添加到mid之后
        node.pre = mid;
        node.next = mid.next;
        mid.next = node;
        node.next.pre = node;
        size++;
        return  true;
    }

    /**
     * 链表的删除
     * @param str : 删除的内容
     * @return : 删除是否成功
     */
    public boolean delete(String str){
        // 判空
        if (size == 0){
            throw new RuntimeException("linked is  null");
        }
        // 判断删除的是否是头结点
        if (head.value.equals(str)){
            if (size == 1){
                head = null;
                tail = null;
            }else {
                head = head.next;
                head.pre = null;
            }
            size--;
            return true;
        }
        // 删除不是头结点
        Node mid = head;
        // 向后移动查找位置:
        // 直到找到 mid的下一个元素是null
        // 或者mid的下一个元素的value就是和str的参数equals
        while (mid.next != null && !mid.next.value.equals(str)){
            mid = mid.next;
        }
        // 如果跳出循环是因为mid移动至末尾
        if (mid.next == null){
            // 没找到
            return false;
        }
        // 删除mid.next
        Node removeNode = mid.next;
        if (removeNode.next != null){// 不是尾结点
            // 删除非尾结点
            removeNode.pre.next = removeNode.next;
            removeNode.next.pre = removeNode.pre;
        } else {// 删除的是尾结点
            tail = tail.pre;
            tail.next = null;
        }
        size--;
        return true;
    }

    /**
     *  根据下标在链表中删除一个元素
     * @param index : 对应要删除的下标
     * @return : 被删除的值
     */
    public String delete(int index){
        // 验证参数是否合法
        if (index < 0 || index >= size) {
            throw  new IllegalArgumentException("index is Illegal");
        }
        // 删除头结点
        if (index == 0){
            String oldValue = head.value;
            if (size == 1){
                head = null;
                tail = null;
            }else {
                head = head.next;
                head.pre = null;
            }
            size--;
            return oldValue;
        }
        // 删除的不是头结点,
        // 找到要删除结点的之前的一个结点, 再删除
        Node mid = head;
        if (index > size/2){// 接近于尾部
            int tag = size;
            mid = tail;
            while (tag != index){
                mid = mid.pre;
                tag--;
            }
        } else {// 接近于头部
            int tag = 1;
            mid = head;
            while (tag != index){
                mid = mid.next;
                tag++;
            }
        }
        // mid 是要删除结点的前一个结点
        Node removeNode = mid.next;
        String oldValue = removeNode.value;
        // 要删除的结点是不是尾结点
        if (removeNode.next == null){// 要删除的结点是尾结点
            tail = tail.pre;
            tail.next = null;
        }else {// 删除的不是尾结点, 也不是头结点
            removeNode.next.pre = removeNode.pre;
            removeNode.pre.next = removeNode.next;
        }
        size--;
        return oldValue;
    }

    /**
     *  替换功能 根据指定内容替换第一个匹配的节点的内容
     * @param oldValue 旧内容
     * @param newValue 新内容
     * @return 返回成功与否
     */
    public boolean set(String oldValue, String newValue) {
        // 判空
        if(size == 0) {
            throw new RuntimeException("The linked is null");
        }
        // 设置标记节点
        // 一个从头指针遍历 一个从尾指针遍历
        Node tagHead = head;
        Node tagTail = tail;
        // 当两个指针没有相遇时进入循环
        while(tagHead != tagTail) {
            // 当其中一个指针指向空时表示全部遍历完毕
            if(tagHead == null || tagTail == null) {
                break;
            }
            if(tagHead.value.equals(oldValue)) {
                tagHead.value = newValue;
                return true;
            }
            if(tagTail.value.equals(oldValue)) {
                tagTail.value = newValue;
                return true;
            }
            tagHead = tagHead.next;
            tagTail = tagTail.pre;
        }
        // 跳出循环且不是因为指向空，表示两个前后指针相遇，此时需要判断相遇的节点是否符合
        if(tagHead != null && tagHead.value.equals(oldValue)) {
            tagHead.value = newValue;
            return true;
        }
        return false;
    }

    /**
     *  替换功能 根据指定内容替换第一个匹配的节点的内容
     * @param index 旧内容
     * @param str 新内容
     * @return 返回替换的旧值
     */
    public String set(int index, String str) {
        // 判空
        if(size == 0) {
            throw new RuntimeException("The linked is null");
        }
        // 判断参数index
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("The index is Illegal");
        }
        int tag = 0;
        Node mid = head;
        // 遍历的元素不是null(后面还有元素可以遍历),  并且遍历的元素和查找的值不相等
        while (mid != null && tag != index ){
            mid = mid.next;
            tag++;
        }
        // 如果跳出循环是因为mid移至末尾
        if (mid == null){
            return null;
        }
        // 否则跳出循环是因为mid匹配到指定内容
        // mid就是要替换的元素
        String oldValue = mid.value;
        mid.value = str;
        return oldValue;
    }

    /**
     * 判断一个元素在链表中是否存在
     * @param str:  要判断的元素
     * @return : Exist or not
     */
    public boolean contains(String str){
        // 判空
        if(size == 0) {
            throw new RuntimeException("The linked is null");
        }
        // 设置标记节点
        // 一个从头指针遍历 一个从尾指针遍历
        Node tagHead = head;
        Node tagTail = tail;
        // 当两个指针没有相遇时进入循环
        while(tagHead != tagTail) {
            // 当其中一个指针指向空时表示全部遍历完毕
            if(tagHead == null || tagTail == null) {
                break;
            }
            if(tagHead.value.equals(str)) {
                return true;
            }
            if(tagTail.value.equals(str)) {
                return true;
            }
            tagHead = tagHead.next;
            tagTail = tagTail.pre;
        }
        // 当循环不是因为指向空而跳出时，表示相遇，需要判断此时节点是否符合条件
        if (tagHead != null && tagHead.value.equals(str)) {
            return true;
        }
        return false;
    }

    /**
     * 根据下标查找一个值
     * @param index : 要查找的下标
     * @return: 这个下标对应的值
     */
    public String get(int index) {
        // 判断链表是不空
        if (size == 0) {
            throw new RuntimeException("linked is null");
        }
        // 判断参数
        if(index <0 || index >= size) {
            throw  new IllegalArgumentException("The index is Illegal");
        }
        int tag = 0;
        Node mid = head;
        // 遍历的元素不是null(后面还有元素可以遍历),  并且遍历的元素和查找的值不相等
        while (mid != null && tag != index){
            mid = mid.next;
            tag++;
        }
        if (mid == null){
            return null;
        }
        return mid.value;
    }

    @Override
    public String toString() {
        return "{" + head +
                ", size=" + size +
                '}';
    }

    class Node {
        // 前后指针
        Node pre;
        String value;
        Node next;
        public Node(Node pre , String value, Node next) {
            this.pre = pre;
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            String preValue = null;
            if (pre != null){
                preValue = pre.value;
            }
            return "{" +
                    "p='" + preValue + '\'' +
                    ", v='" + value + '\'' +
                    ", n=" + next +
                    '}';
        }
    }
}
